#include "utils/hash_queue.hpp"
#include "utils/hash_queue-impl.hpp"

/**
 * \file
 * \ingroup utility
 * \brief cas::hash_queue implementation.
 */

namespace cas
{
    SLOG_COMPONENT_DEFINE("HashQueue");

    template <class K, class T>
    hash_queue<K, T>::hash_queue()
    {
        SLOG_FUNCTION_NOARGS();
    }

    template <class K, class T>
    hash_queue<K, T>::~hash_queue()
    {
        SLOG_FUNCTION_NOARGS();
    }

    template <class K, class T>
    inline size_t hash_queue<K, T>::capacity() const
    {
        SLOG_FUNCTION_NOARGS();
        return pool_size;
    }

    template <class K, class T>
    void hash_queue<K, T>::clear()
    {
        SLOG_FUNCTION_NOARGS();
        if (pool)
        {
            delete[] pool;
            pool = nullptr;
        }
        list_map.clear();
        used_size = item_size = 0;
        list_head = list_tail = list_free = SIZE_MAX;
    }

    template <class K, class T>
    void hash_queue<K, T>::resize(const size_t &size)
    {
        SLOG_FUNCTION(size);
        if (size == 0)
        {
            SFATAL_ERROR_CONT("size must be positive");
            return;
        }
        if (pool && size < pool_size)
        {
            SFATAL_ERROR_CONT("size < poolSize, must clear before");
            return;
        }

        if (pool == nullptr)
        {
            // init
            pool = new hash_queue_node[size];
            list_map.clear();
            used_size = item_size = 0;
            list_head = list_tail = list_free = SIZE_MAX;
        }
        else if (size > pool_size)
        {
            // expansion, keep list_map
            auto new_pool = new hash_queue_node[size];                   // temporary
            memcpy(new_pool, pool, sizeof(hash_queue_node) * pool_size); // \note unsafe here
            delete[] pool;
            pool = new_pool; // pointer to new location
        }

        SASSERT(pool != nullptr);
        pool_size = size; // update capacity
    }

    template <class K, class T>
    inline size_t hash_queue<K, T>::size() const
    {
        SLOG_FUNCTION_NOARGS();
        return item_size;
    }

    template <class K, class T>
    inline void hash_queue<K, T>::erase(const K &key)
    {
        const auto it = list_map.find(key);
        if (likely(it != list_map.end()))
        {
            internal_erase(it->second);
        }
    }

    template <class K, class T>
    inline void hash_queue<K, T>::erase(const size_t &index)
    {
        SASSERT(index >= 0 && index < used_size);
        internal_erase(index);
    }

    template <class K, class T>
    inline typename hash_queue<K, T>::hash_queue_iterator hash_queue<K, T>::find(K key)
    {
        return list_map.find(key);
    }

    template <class K, class T>
    inline T *const hash_queue<K, T>::get(const K &key)
    {
        const auto it = list_map.find(key);
        return &(pool[it->second].data);
    }

    template <class K, class T>
    inline T *const hash_queue<K, T>::get(const size_t &index)
    {
        SASSERT(index >= 0 && index < used_size);
        return &(pool[index].data);
    }

    template <class K, class T>
    inline typename hash_queue<K, T>::hash_queue_iterator hash_queue<K, T>::map_end()
    {
        return list_map.end();
    }

    template <class K, class T>
    void hash_queue<K, T>::move_back(const size_t &index)
    {
        SLOG_FUNCTION(index);
        SASSERT(index >= 0 && index < used_size && list_tail != SIZE_MAX);
        if (index != list_tail)
        {
            // move to tail of linked list
            auto &it = pool[index];
            SASSERT(it.next != SIZE_MAX);
            pool[it.next].prev = it.prev; // maybe SIZE_MAX
            if (unlikely(index == list_head))
            {
                SASSERT(it.prev == SIZE_MAX);
                list_head = it.next; // shift list head
            }
            else
            {
                SASSERT(it.prev != SIZE_MAX);
                pool[it.prev].next = it.next; // update prev node's next
            }

            it.prev = list_tail;
            it.next = SIZE_MAX;           // point to null
            pool[list_tail].next = index; // update tail node's next
            list_tail = index;            // shift tail
        }
    }

    template <class K, class T>
    void hash_queue<K, T>::move_back(const K &key)
    {
        SLOG_FUNCTION_NOARGS();
        const auto it = list_map.find(key);
        if (it != list_map.end())
        {
            move_back(it->second);
        }
    }

    template <class K, class T>
    void hash_queue<K, T>::move_front(const size_t &index)
    {
        SLOG_FUNCTION(index);
        SASSERT(index >= 0 && index < used_size && list_head != SIZE_MAX);
        if (index != list_head)
        {
            // move to head of linked list
            auto &it = pool[index];
            SASSERT(it.prev != SIZE_MAX);
            pool[it.prev].next = it.next; // maybe SIZE_MAX
            if (unlikely(index == list_tail))
            {
                SASSERT(it.prev == SIZE_MAX);
                list_tail = it.prev; // shift list tail
            }
            else
            {
                SASSERT(it.prev != SIZE_MAX);
                pool[it.next].prev = it.prev; // update next node's prev
            }

            it.next = list_head;
            it.prev = SIZE_MAX;           // point to null
            pool[list_head].prev = index; // update head node's prev
            list_head = index;            // shift head
        }
    }

    template <class K, class T>
    void hash_queue<K, T>::move_front(const K &key)
    {
        SLOG_FUNCTION_NOARGS();
        const auto it = list_map.find(key);
        if (it != list_map.end())
        {
            move_front(it->second);
        }
    }

    template <class K, class T>
    bool hash_queue<K, T>::push_back(K key, T data)
    {
        SLOG_FUNCTION_NOARGS();
        bool is_evict = false;
        size_t idx = SIZE_MAX;

        if (used_size < pool_size)
        {
            idx = used_size++; // increase used_size
        }
        else if (item_size < used_size)
        {
            SASSERT_MSG(list_free != SIZE_MAX, "error free list");
            idx = list_free;            // use free list
            list_free = pool[idx].free; // pop head of free list
        }
        else
        {
            if (!evict_front)
            {
                return true; // evict_front disabled, do nothing
            }
            is_evict = true; // used_size == pool_size && item_size == pool_size
            SASSERT_MSG(list_head != SIZE_MAX, "error linked list");
            idx = list_head;               // evict list head
            list_map.erase(pool[idx].key); // delete index
            if (item_size == 1)
            {
                SASSERT(list_head == list_tail);
                list_head = list_tail = SIZE_MAX; // become empty
            }
            else
            {
                list_head = pool[idx].next; // shift head
                pool[list_head].prev = SIZE_MAX;
            }
            item_size--; // deleted
        }

        SASSERT(idx != SIZE_MAX);
        pool[idx].key = key;        // assign key
        pool[idx].data = data;      // \note may cause memory leak
        pool[idx].prev = list_tail; // SIZE_MAX if empty list
        pool[idx].next = pool[idx].free = SIZE_MAX;

        if (list_tail != SIZE_MAX)
        {
            pool[list_tail].next = idx; // update tail
        }
        else
        {
            SASSERT(item_size == 0); // empty list
            list_head = idx;         // init head
        }
        list_tail = idx; // shift tail

        list_map[key] = idx; // update index
        item_size++;         // count new item
        return is_evict;
    }

    template <class K, class T>
    bool hash_queue<K, T>::push_front(K key, T data)
    {
        SLOG_FUNCTION_NOARGS();
        bool is_evict = false;
        size_t idx = SIZE_MAX;

        if (used_size < pool_size)
        {
            idx = used_size++; // increase used_size
        }
        else if (item_size < used_size)
        {
            SASSERT_MSG(list_free != SIZE_MAX, "error free list");
            idx = list_free;            // use free list
            list_free = pool[idx].free; // pop head of free list
        }
        else
        {
            if (!evict_back)
            {
                return true; // evict_back disabled, do nothing
            }
            is_evict = true; // used_size == pool_size && item_size == pool_size
            SASSERT_MSG(list_tail != SIZE_MAX, "error linked list");
            idx = list_tail;               // evict list tail
            list_map.erase(pool[idx].key); // delete index
            if (item_size == 1)
            {
                SASSERT(list_head == list_tail);
                list_head = list_tail = SIZE_MAX; // become empty
            }
            else
            {
                list_tail = pool[list_tail].prev; // shift tail
                pool[list_tail].next = SIZE_MAX;  // pop tail of linked list, may become empty
            }
            item_size--; // deleted
        }

        SASSERT(idx != SIZE_MAX);
        pool[idx].key = key;        // assign key
        pool[idx].data = data;      // \note may cause memory leak
        pool[idx].next = list_head; // SIZE_MAX if empty list
        pool[idx].prev = pool[idx].free = SIZE_MAX;

        if (list_head != SIZE_MAX)
        {
            pool[list_head].prev = idx; // update head
        }
        else
        {
            SASSERT(item_size == 0); // empty list
            list_tail = idx;         // init tail
        }
        list_head = idx; // shift head

        list_map[key] = idx; // insert index
        item_size++;         // count new item
        return is_evict;
    }

    template <class K, class T>
    typename hash_queue<K, T>::hash_queue_pair hash_queue<K, T>::pop_back()
    {
        SLOG_FUNCTION_NOARGS();
        SASSERT(item_size > 0 && list_tail != SIZE_MAX);
        const hash_queue_pair ret = std::make_pair(pool[list_tail].key, pool[list_tail].data);
        internal_erase(list_tail);
        return ret;
    }

    template <class K, class T>
    typename hash_queue<K, T>::hash_queue_pair hash_queue<K, T>::pop_front()
    {
        SLOG_FUNCTION_NOARGS();
        SASSERT(item_size > 0 && list_head != SIZE_MAX);
        const hash_queue_pair ret = std::make_pair(pool[list_head].key, pool[list_head].data);
        internal_erase(list_head);
        return ret;
    }

    template <class K, class T>
    void hash_queue<K, T>::set_eviction(uint8_t policy)
    {
        evict_back = policy & 2;
        evict_front = policy & 1;
    }

    template <class K, class T>
    void hash_queue<K, T>::internal_erase(const size_t &index)
    {
        SASSERT(index >= 0 && index < used_size && item_size > 0);
        auto &it = pool[index];

        if (index + 1 == used_size)
        {
            used_size--; // shrink used_size
        }
        else
        {
            it.free = list_free; // mark free space
            list_free = index;   // push head of free list
        }

        if (item_size == 1)
        {
            SASSERT(list_head == list_tail);  // check size=1
            list_head = list_tail = SIZE_MAX; // become empty
        }
        else
        {
            // more then 1 item
            if (index != list_head)
            {
                SASSERT(it.prev != SIZE_MAX); // previous node
                pool[it.prev].next = it.next; // shift pointer
                if (index != list_tail)
                {
                    SASSERT(it.next != SIZE_MAX); // next node
                    pool[it.next].prev = it.prev; // shift pointer
                }
                else
                {
                    SASSERT(it.next == SIZE_MAX); // list tail
                    list_tail = it.prev;          // shift tail
                }
            }
            else
            {
                SASSERT(it.prev == SIZE_MAX && it.next != SIZE_MAX); // is list head
                pool[it.next].prev = it.prev;                        // shift pointer
                list_head = it.next;                                 // shift head
            }
        }

        list_map.erase(it.key);       // delete index
        item_size--;                  // reduce item counter
        it.prev = it.next = SIZE_MAX; // for safety
    }
} // namespace cas
